基于混合离散粒子群优化的轨道分配算法

doi:10.16451/j.cnki.issn1003-6059.201908009

Abstract
Figure/Table
References (26)
Related Citation (2)

Download: PDF (819 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract

Most of the existing track allocation works neglect the local nets problem, and are prone to fall into the local extremums. Based on discrete particle swarm optimization, genetic operation and negotiation-based refining strategy, a track assignment algorithm is proposed by considering local nets, overlapping conflict, wirelength and blockages. The algorithm abstracts local nets and constructs the corresponding model of segments. To expand population diversity, hybrid genetic operation is incorporated to improve the efficiency of global search. At the same time, a simple and efficient fitness function is designed. Finally, the negotiation-based refining strategy is exploited to further reduce the overlap of segments. The experimental results indicate the effectiveness of the proposed algorithm. The algorithm can obtain better overlapping cost index optimization value and reduce the congestion in the key routing area.

Key words： Track Assignment Very Large Scale Integration Discrete Particle Swarm Optimization Local Nets Genetic Operator

Received: 13 May 2019

ZTFLH:

TP 301

Fund:

Supported by National Natural Science Foundation of China(No.61877010,11501114), Natural Science Foundation of Fujian Province(No.2019J01243)

Corresponding Authors: LIU Genggeng(Corresponding author), Ph.D., associate professor. His research interests include computational intelligence and its application.

About author:: GUO Wenzhong, Ph.D., professor. His research interests include computational intelligence and its application.CHEN Xiaohua, master student. Her research interests include EDA design algorithm.CHEN Guolong, Ph.D., professor. His research interests include artificial intelligence and network information security.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	GUO Wenzhong
	CHEN Xiaohua
	LIU Genggeng
	CHEN Guolong

Cite this article:

GUO Wenzhong,CHEN Xiaohua,LIU Genggeng等. Track Assignment Algorithm Based on Hybrid Discrete Particle Swarm Optimization[J]. , 2019, 32(8): 758-770.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.201908009 OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2019/V32/I8/758

[1] 徐宁,洪先龙.超大规模集成电路物理设计理论与算法.北京:清华大学出版社, 2009.
(XU N, HONG X L. Very Large Scale Integration Physical Design Theory and Method. Beijing, China: Tsinghua University Press, 2009.)
[2] CHO M, XIANG H, PURI R, et al. Track Routing and Optimization for Yield. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(5): 872-882.
[3] GAO X, MACCHIARLO L. Track Routing Optimizing Timing and Yield // Proc of the 16th Asia and South Pacific Design Automation Conference. Washington, USA: IEEE, 2011: 627-632.
[4] CHANG Y N, LI Y L, LIN W T, et al. Non-slicing Floorplanning Based Crosstalk Reduction on Gridless Track Assignment for a Gridless Routing System with Fast Pseudo-Tile Extraction // Proc of the ACM Interntaional Symposium on Physical Design. New York, USA: ACM, 2008: 134-141.
[5] BATTERYWALA S, SHENOY N, NICHOLLS W, et al. Track Assignment: A Desirable Intermediate Step between Global Routing and Detailed Routing // Proc of the IEEE/ACM International Conference on Computer Aided Design. Washington, USA: IEEE, 2002: 59-66.
[6] LAI B T, LI T H, CHEN T C. Native-Conflict-Avoiding Track Routing for Double Patterning Technology // Proc of the IEEE International SOC Conference. Washington, USA: IEEE, 2012. 381-386.
[7] WONG M P, LIU W H, WANG T C. Negotiation-Based Track Assignment Considering Local Nets // Proc of the 21st Asia and South Pacific Design Automation Conference(ASP-DAC). Washington, USA: IEEE, 2016: 378-383.
[8] 郭文忠,陈国龙.一种求解多目标最小生成树问题的有效离散粒子群优化算法.模式识别与人工智能, 2009, 22(4): 597-604.
(GUO W Z, CHEN G L. An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-criteria Minimum Spanning Tree. Pa-ttern Recognition and Artificial Intelligence, 2009, 22(4): 597-604.)
[9] MUDJIHARTONO P, JIAMTHAPTHAKSIN R, TANPRASERT T. Parallelized GA-PSO Algorithm for Solving Job Shop Scheduling Problem // Proc of the 2nd International Conference on Science in Information Technology. Washington, USA: IEEE, 2016: 103-108.
[10] 钟一文,蔡荣英.求解二次分配问题的离散粒子群优化算法.自动化学报, 2007, 33(8): 871-874.
(ZHONG Y W, CAI R Y. Discrete Particle Swarm Optimization Algorithm for QAP. Acta Automatica Sinica, 2007, 33(8): 871- 874.)
[11] DU J X, HUANG D S, ZHANG J, et al. Shape Matching Using Fuzzy Discrete Particle Swarm Optimization // Proc of the IEEE Swarm Intelligence Symposium. Washington, USA: IEEE, 2005: 405-408.
[12] SHARMA A, KAPUR R K. Image Enhancement Using Hybrid GSA-Particle Swarm Optimization // Proc of the 2nd International Conference on Contemporary Computing and Informatics. Washington, USA: IEEE, 2016: 698-704.
[13] TOREINI E, MEHRNEJAD M. Clustering Data with Particle Swarm Optimization Using a New Fitness // Proc of the 3rd Conference on Data Mining and Optimization. Washington, USA: IEEE, 2011: 266-270.
[14] WANG C, ZHANG Y, SONG J B, et al. A Novel Optimized SVM Algorithm Based on PSO with Saturation and Mixed Time-Delays for Classification of Oil Pipeline Leak Detection. Systems Science and Control Engineering, 2019, 7(1): 75-88.
[15] PRAKASH A, LAL R K. PSO: An Approach to Multiobjective VLSI Partitioning // Proc of the International Conference on Innovations in Information, Embedded and Communication Systems. Washington, USA: IEEE, 2015. DOI: 10.1109/ICIIECS.2015.7192971.
[16] GUO W Z, LIU G G, CHEN G L, et al. A Hybrid Multi-objective PSO Algorithm with Local Search Strategy for VLSI Partitioning. Frontiers of Computer Science, 2014, 8(2): 203-216.
[17] CHEN G L, GUO W Z, CHEN Y Z. A PSO-Based Intelligent Decision Algorithm for VLSI Floorplanning. Soft Computing, 2010, 14(12): 1329-1337.
[18] SIVARANJANI P, KUMAR A S. Thermal-Aware Non-slicing VLSI Floorplanning Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm. Circuits, Systems, and Signal Processing, 2015, 34(11): 3521-3542.
[19] KARIMI G, AKBARPOUR H, SADEGHZADEH A. Multi Objective Particle Swarm Optimization Based Mixed Size Module Placement in VLSI Circuit Design. Applied Mathematics and Information Sciences, 2015, 9(3): 1485-1492.
[20] LIU G G, HUANG X, GUO W Z, et al. Multilayer Obstacle-Avoiding X-Architecture Steiner Minimal Tree Construction Based on Particle Swarm Optimization. IEEE Transactions on Cybernetics, 2015, 45(5): 1003-1016.
[21] 刘耿耿,陈志盛,郭文忠,等.基于自适应PSO和混合转换策略的X结构Steiner最小树算法.模式识别与人工智能, 2018, 31(5): 398-408.
(LIU G G, CHEN Z S, GUO W Z, et al. Self-adapting PSO Algorithm with Efficient Hybrid Transformation Strategy for X-Architecture Steiner Minimal Tree Construction Algorithm. Pattern Recognition and Artificial Intelligence, 2018, 31(5): 398-408.)
[22] VISWANATHAN N, ALPERT C, SZE C, et al. The DAC 2012 Routability-Driven Placement Contest and Benchmark Suite // Proc of the 49th Annual Design Automation Conference. New York, USA: ACM, 2012: 774-782.
[23] HSU M K, CHEN Y F, HUANG C C, et al. Routability-Driven Placement for Hierarchical Mixed-Size Circuit Designs // Proc of the 50th Annual Design Automation Conference. New York, USA: ACM, 2013. DOI: 10.1145/2463209.2488921.
[24] LIU W H, KAO W C, LI Y L, et al. Multithreaded Collision-Aware Global Routing with Bounded-Length Maze Routing // Proc of the 47th Design Automation Conference. New York, USA: ACM, 2013: 709-722.
[25] KIM M C, HU J, LEE D J, et al. A SimPLR Method for Routabi-lity-Driven Placement // Proc of the International Conference on Computer-Aided Design. Washington, USA: IEEE, 2011: 67-73.
[26] HE X, HUANG T, XIAO L F, et al. Ripple: An Effective Rou-tability-Driven Placer by Iterative Cell Movement // Proc of the IEEE/ACM International Conference on Computer-Aided Design. Washington, USA: IEEE, 2011: 74-79.